#ifndef DEQUE_H
#define DEQUE_H

/**
 *  //sz 为元素A的大小，如果元素A大小 大于 512 则一个缓冲区放入一个元素。
    //反则就放入 size_t(512 / sizeof(A)) 个数量
    inline size_t __deque_buf_size(size_t n, size_t sz)
    { return n != 0 ? n :( sz < 512 ? size_t(512 / sz) :size_t(1) );}
**/
inline size_t _deque_buf_size(size_t n, size_t sz)
{
    return n != 0 ? n : ( sz < 512 ? size_t(512/sz) : size_t(1));
}

template <class T, class Ref, class Ptr, size_t BufSize>
struct __deque_iterator {
    typedef random_access_iterator_tag iterator_catogory;   //随机访问迭代器的类型
    typedef T value_type;
    typedef Ptr pointer;
    typedef Ref reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef T** map_pointer;
    typedef __deque_iterator self;

    T* cur;//元素的位置
    T* first;//缓冲区的头部
    T* last;//缓冲区的尾部
    map_pointer node;

    reference operator*() const { return *cur; }
    pointer operator->() const { return &(operator *());}

    self & operator++()
    {
        ++cur;                      //切换到下一个元素
        if (cur == last) {          //如果抵达缓冲区尾端
            set_node(node + 1);     //就切换到下一个节点
            cur = first;            //cur 再指向于 first    cur 是指向缓冲区的元素，first 和 end 是缓冲区的首尾元素
        }

        return * this;
    }

    self operator ++(int)
    {
        self tmp = *this;
        ++*this;
        return tmp;
    }

    difference_type operator-(const self& x) const
    {
        //buffer_size 等同于  _deque_buf_size
        return difference_type(buffer_size()) * (node - x.node - 1) +
                (cur - first) + (x.last - x.cur);
        /**
          node - x.node - 1 其中减一的原因是，x.node 所在的buff 上，存在元素未放满的情况
*/
    }

    reference operator[] (difference_type n) const
    { return *(*this + n);}

    /// 依次修改 node first last 的位置
    void set_node(map_pointer new_node)
    {
        node = new_node;
        first = *new_node;
        last = first + difference_type(buffer_size());
    }
};

/**
    BufSiz 指的是每个 buffer 容纳的元素个数
*/
template <class T, class Alloc = alloc,
          size_t BufSize = 0>
class deque {
public:
    typedef T value_type;
    typedef value_type* pointer;
    typedef
    typedef __deque_iterator<T, T&, T*, BufSiz> iterator;//自定义类作为迭代器
    typedef size_t size_type;
protected:
    typedef pointer* map_pointer;
protected:
    iterator start;//指向容器头部的迭代器 ，start.cur 是容器的第一个元素，*start 也是指向容器的第一个元素
    iterator finish;//指向容器尾部的迭代器， finish.cur 是容器的最后一个元素，finish 是指向容器最后一个元素的下一个位置。要取最后一个元素，需要--finish.
    map_pointer map;
    size_type map_size;
public:
    iterator begin() { return start; }
    iterator end() { return finish; }
    size_type size() { return finish - start;}
    size_type max_size() const { return size_type(-1); }
};

#endif // DEQUE_H
